package codeRandomThoughts.Test377组合总和IV;

import java.util.Arrays;

/**
 * 尝试一下用二维数组
 */
public class Solution3 {
    public int combinationSum4(int[] nums, int target) {

        //代表编号0~i的物品凑成target的排列数
        int[][] dp = new int[nums.length][target + 1];

        //初始化矩阵
        for (int i = 0; i < nums.length; i++) {
            dp[i][0] = 1;
        }

        //这里排序是为了使下面dp[i][j - nums[k]]不会越界
        Arrays.sort(nums);

        for (int i = 0; i < nums.length; i++) {//这里两个for循环交换也无所谓
            for (int j = 0; j <= target; j++) {
                if (j >= nums[i]) {
                    //每种排列可以分解为两部分 一部分是前面的排列dp[i][j-nums[k]] 一部分是最后一位数字nums[k]
                    //最后一位可以是nums中的任何数字,所以我们遍历所有数字,然后把这些情况的排列数加起来
                    for (int k = 0; k <= i; k++) {
                        dp[i][j] += dp[i][j - nums[k]];
                    }
                } else {
                    if (i != 0) {
                        dp[i][j] = dp[i - 1][j];
                    }
                }
            }
        }

        System.out.println("dp矩阵");
        for (int i = 0; i < nums.length; i++) {
            for (int j = 0; j <= target; j++) {
                System.out.print(dp[i][j] + " ");
            }
            System.out.print("\n");
        }


        return dp[nums.length - 1][target];
    }
}
